# -*- coding: utf-8 -*-
# @Time    : 2021/1/2 下午12:17
# @Author  : tgy
# https://leetcode-cn.com/problems/partition-list/

from ListNode import ListNode


class Solution:
    def partition(self, head: ListNode, x: int) -> ListNode:
        ...
        frontHead = ListNode(0)
        frontTail = frontHead
        postHead = ListNode(0)
        postTail = postHead

        node = head
        while node:
            if node.val < x:
                frontTail.next = node
                frontTail = node
            else:
                postTail.next = node
                postTail = node

            node = node.next

        frontTail.next = postHead.next
        # 注意，这里要清除最后的next
        postTail.next = None
        return frontHead.next



if __name__ == '__main__':
    ...

    node = ListNode(1)
    node.next = ListNode(4)
    node.next.next = ListNode(2)
    node.next.next.next = ListNode(3)
    solution = Solution()
    list_node = solution.partition(node, 3)
    print(list_node)
